This specification generally relates to a database service. A database client may submit a database operation to a remote database service to add records to a database, search records stored in a database, remove records from a database, or perform other operations on records in a database.